CAS

什么是CAS

CAS（Compare And Swap）指比较并交换。CAS算法CAS(V,E, N)包含3个参数，V表示要更新的变量，E表示预期的值，N表示新值。在且仅在V值等于 E值时，才会将V值设为 N，如果 V值和 E值不同，则说明已经有其他线程做了更新，当前线程什么都不做。最后，CAS返回当前V的真实值。

CAS的特性：乐观锁

CAS操作采用了乐观锁的思想，总是认为自己可以成功完成操作。在有多个线程同时使用CAS操作一个变量时，只有一个会胜出并成功更新，其余均会失败。失败的线程不会被挂起，仅被告知失败，并且允许再次尝试，当然，也允许失败的线程放弃操作。基于这样的原理，CAS操作即使没有锁，也可以发现其他线程对当前线程的干扰，并进行恰当的处理。

CAS自旋等待

在JDK的原子包java.util.concurrent.atomic里面提供了一组原子类，这些原子类的基本特性就是在多线程环境下，在有多个线程同时执行这些类的实例包含的方法时，会有排他性。其内部便是基于CAS算法实现的，即在某个线程进入方法中执行其中的指令时，不会被其他线程打断；而别的线程就像自旋锁一样，一直等到该方法执行完成才由JVM从等待的队列中选择另一个线程进入。

相对于synchronized阻塞算法，CAS是非阻塞算法的一种常见实现。由于CPU的切换比CPU指令集的操作更加耗时，所以CAS的自旋操作在性能上有了很大的提升。

ABA

对CAS算法的实现有一个重要的前提：需要取出内存中某时刻的数据，然后在下一时刻进行比较、替换，在这个时间差内可能数据已经发生了变化，导致产生ABA问题。

ABA问题指第1个线程从内存的V位置取出A，这时第2个线程也从内存中取出A，并将V位置的数据首先修改为B，接着又将V位置的数据修改为A，这时第1个线程在进行CAS操作时会发现在内存中仍然是A，然后第1个线程操作成功。尽管从第1个线程的角度来说，CAS操作是成功的，但在该过程中其实V位置的数据发生了变化，只是第1个线程没有感知到罢了，这在某些应用场景下可能出现过程数据不一致的问题。

部分乐观锁是通过版本号（version）来解决ABA问题的，具体的操作是乐观锁每次在执行数据的修改操作时都会带上一个版本号，在预期的版本号和数据的版本号一致时就可以执行修改操作，并对版本号执行加1操作，否则执行失败。因为每次操作的版本号都会随之增加，所以不会出现ABA问题，因为版本号只会增加，不会减少。

AQS

AQS(Abstract Aueued Synchronizer)是一个抽象的队列同步器，通过维护一个共享资源状态（Volatile Int State) 和一个先进先出（FIFO）的线程等待队列来实现一个多线程访问共享资源的同步框架。

AQS的原理

AQS为每个共享资源都设置一个共享资源锁，线程在需要访问共享资源时首先需要获取共享资源锁，如果获取到了共享资源锁，便可以在当前线程中使用该共享资源，如果获取不到，则将该线程放入线程等待队列，等待下一次资源调度。许多同步类的实现都依赖于AQS，例如常用的ReentrantLock、Semaphore和CountDownLatch。

state：状态

Abstract Queued Synchronizer维护了一个volatile int类型的变量，用于表示当前的同步状态。Volatile虽然不能保证操作的原子性，但是能保证当前变量state的可见性。state的访问方式有三种：getState()、setState()和compareAndSetState()，均是原子操作，其中，compareAndSetState的实现依赖于Unsafe的compareAndSwapInt()。

AQS共享资源的方式：独占式和共享式

AQS定义了两种资源共享方式：独占式（Exclusive）和共享式（Share）。

独占式：只有一个线程能执行，具体的Java实现有ReentrantLock。
共享式：多个线程可同时执行，具体的Java实现有Semaphore和CountDownLatch。

AQS只是一个框架，只定义了一个接口，具体资源的获取、释放都交由自定义同步器去实现。不同的自定义同步器争用共享资源的方式也不同，自定义同步器在实现时只需实现共享资源state的获取与释放方式即可，至于具体线程等待队列的维护，如获取资源失败入队、唤醒出队等，AQS已经在顶层实现好，不需要具体的同步器再做处理。

同步器的实现是AQS的核心内存。ReentrantLock对AQS的独占方式实现为：ReentrantLock中的state初始值为0时表示无锁状态。在线程执行tryAcquire()获取该锁后ReentrantLock中的state+1，这时该线程独占ReentrantLock锁，其他线程在通过tryAcquire()获取锁时均会失败，直到该线程释放锁后state再次为0，其他线程才有机会获取该锁。该线程在释放锁之前可以重复获取此锁，每获取一次便会执行一次state+1，因此ReentrantLock也属于可重入锁。但获取多少次锁就要释放多少次锁，这样才能保证state最终为0。如果获取锁的次数多于释放锁的次数，则会出现该线程一直持有该锁的情况；如果获取锁的次数少于释放锁的次数，则运行中的程序会报锁异常。

CountDownLatch对AQS的共享方式实现为：CountDownLatch将任务分为N个子线程去执行，将state也初始化为N, N与线程的个数一致，N个子线程是并行执行的，每个子线程都在执行完成后countDown()一次，state会执行CAS操作并减1。在所有子线程都执行完成（state=0）时会unpark()主线程，然后主线程会从await()返回，继续执行后续的动作。

一般来说，自定义同步器要么采用独占方式，要么采用共享方式，实现类只需实现tryAcquire、tryRelease或tryAcquireShared、tryReleaseShared中的一组即可。但AQS也支持自定义同步器同时实现独占和共享两种方式，例如ReentrantReadWriteLock在读取时采用了共享方式，在写入时采用了独占方式。